package codeRandomThoughts.Test131分割回文串;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    public List<List<String>> result = new ArrayList<>();
    public List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String s, int startIndex) {
        //遍历到字符串的末尾时,回溯结束
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        //单层递归逻辑
        for (int i = startIndex; i < s.length(); i++) {
            String substring = s.substring(startIndex, i + 1);
            if (isPalindrome(substring)) {
                path.add(substring);
            } else {
                continue;
            }

            backtracking(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    public boolean isPalindrome(String s) {
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;
        while (i < j) {
            if (chars[i] != chars[j]) return false;
            i++;
            j--;
        }
        return true;
    }
}
